package mySort;

//快速排序
public class QuickSort {

    //方法一：Hoare方法，返回值是基准值下标
    public int partitionHoare(int[] arr, int left, int right) {
        int key = left; //把key定在左边，那右指针就要先走
        //右边找比基准值小的，左边找基准值大的
        while (left < right) {
            while (left < right && arr[right] >= arr[key]) {
                right--;
            }
            while (left < right && arr[left] <= arr[key]) {
                left++;
            }
            swap(arr, left, right);
        }
        swap(arr, left, key);
        return left;
    }

    //方法二：挖坑法，返回值是基准值下标
    public int partitionHole(int[] arr, int left, int right) {
        int key = left;
        while (left < right) {
            //跳过大于基准值的元素
            while (left < right && arr[right] >= arr[key]) {
                right--;
            }
            arr[left] = arr[right];
            while (left < right && arr[left] <= arr[key]) {
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] = arr[key];
        return left;
    }

    //方法三：双指针法，返回值是基准值下标
    public int partitionPtr(int[] arr, int left, int right) {
        int key = left;
        //precess 和 i 需要从key后第一个位置开始同步走
        // i 指针负责往前面探路，precess指针负责等待交换，而precess的元素都满足小于基准值
        int precess = left + 1;
        for (int i = precess; i <= right; i++) {
            if (arr[i] < arr[key]) {  //小于基准值的元素放到前面的了，这里不能等于
                swap(arr, i, key);
                precess++;
            }
        }
        swap(arr, precess - 1, left);//注意参与交换的元素
        return precess - 1;
    }

    //第一次优化
    /*public void helperBetter(int[] arr, int start, int end) {
        if (start >= end) {
            return ;
        }
        if (start - end < 250) {  //当趋于有序的时候改为直接插入排序
            insertSortRange(arr, start, end);
            return;
        }
        int pivot = partitionHoare(arr, start, end);
        helper(arr, start, pivot - 1);
        helper(arr, pivot + 1, end);
    }*/

    //三数取中法
    private int threeOfMid(int[] arr, int start, int end) {
        int mid = start + ((end - start) >>> 1);
        if (arr[start] < arr[end]) {
            if (arr[mid] < arr[start]) {
                return start;
            } else if (arr[end] < arr[mid]) {
                return end;
            } else {
                return mid;
            }
        } else {
            if (arr[end] > arr[mid]) {
                return mid;
            } else if (arr[mid] > arr[start]) {
                return start;
            } else {
                return mid;
            }
        }
    }

    //优化最终版（三数取中法）
    public void helperBetter(int[] arr, int start, int end) {
        if (start >= end) {
            return ;
        }
        if (start - end < 250) {  //当趋于有序的时候改为直接插入排序
            insertSortRange(arr, start, end);
            return;
        }
        //三数取中法
        int index = threeOfMid(arr, start, end); //尽量找到中间大的元素并交换
        swap(arr, index, start);

        int pivot = partitionHoare(arr, start, end); //根据基准值排列

        helper(arr, start, pivot - 1);
        helper(arr, pivot + 1, end);
    }

    //分别为开始下标和结束下标
    public void helper(int[] arr, int start, int end) {
        if (start >= end) { //有效区间为 1 或者 0 就返回
            return;
        }
        int pivot = partitionHoare(arr, start, end); //返回基准值下标
        helper(arr, start, pivot - 1);
        helper(arr, pivot + 1, end);
    }

    //快速排序主体
    public void quickSort(int[] arr) {
        helperBetter(arr, 0, arr.length - 1);
    }

    //交换数组元素
    public void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    //插入排序
    public void insertSortRange(int[] arr, int start, int end) {
        for (int i = start + 1; i <= end; i++) {
            int tmp =  arr[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                if (arr[j] > tmp) {
                    arr[j + 1] = arr[j];
                } else {
                    break;
                }
            }
            arr[j + 1] =tmp;
        }
    }
}
